package com.yuanzhi.train.dynamic.programming;

/**
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例 1：
 *
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 示例 2：
 *
 * 输入：nums = [1] 输出：1 示例 3：
 *
 * 输入：nums = [0] 输出：0 示例 4：
 *
 * 输入：nums = [-1] 输出：-1 示例 5：
 *
 * 输入：nums = [-100000] 输出：-100000   提示： 1 <= nums.length <= 3 * 104 -105 <=
 * nums[i] <= 105
 *
 * @author yuanZhi
 * @since 2021/4/2 15:21
 */
public class MaxSubArray {
	public static int maxSubArray(int[] nums) {
		// 记录下前几个之和以及最大和（当数组只有一个元素时区第一个，所以最大和初始化为数组第一个元素）
		int preSum = 0, maxSum = nums[0];
		// 循环比较前几个之和加上当前元素与当前元素，取较大者（得出前几个最大和为多少）
		// 之后再与记录的最大和比较，取大者
		for (int num : nums) {
			preSum = Math.max(preSum + num, num);
			maxSum = Math.max(maxSum, preSum);
		}
		return maxSum;
	}

    /**
     * 暴力法
     */
	public static int solution(int[] nums) {
	    // 记录最大和
	    int max = nums[0];
	    int temp;
        for (int i = 0; i < nums.length; i++) {
            // 以num[i]结尾的连续子数组的最大和
            temp = 0;
            for (int num : nums) {
                temp += num;
                if (max < temp) {
                    max = temp;
                }
            }
        }
        return max;
    }

	public static void main(String[] args) {
		System.out.println(
				maxSubArray(new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 }));
		System.out.println(maxSubArray(new int[] { 1 }));
		System.out.println(maxSubArray(new int[] { 0 }));
		System.out.println(maxSubArray(new int[] { -1 }));
		System.out.println(maxSubArray(new int[] { -1000000 }));
	}
}
